package com.cat.greedyAlgorithm;

import java.util.HashMap;
import java.util.Map;

public class OptimizedLongestBalancedSubstring {
    public static int longestBalancedSubstring(String s) {
        int n = s.length();
        if (n <= 1) return n;
        
        // 存储计数差异模式的首次出现索引
        Map<String, Integer> patternMap = new HashMap<>();
        // 初始状态：三个字符计数都为0
        patternMap.put("0,0,0", -1);
        
        int countA = 0, countB = 0, countC = 0;
        int maxLength = 0;
        
        for (int i = 0; i < n; i++) {
            // 更新当前字符的计数
            char c = s.charAt(i);
            if (c == 'a') countA++;
            else if (c == 'b') countB++;
            else if (c == 'c') countC++;
            
            // 计算计数差异，使用相对值避免大数问题
            int diffAB = countA - countB;
            int diffBC = countB - countC;
            int diffAC = countA - countC;
            
            // 生成差异模式的键
            String pattern = diffAB + "," + diffBC + "," + diffAC;
            
            // 如果模式已存在，说明从首次出现位置到当前位置是平衡子串
            if (patternMap.containsKey(pattern)) {
                int length = i - patternMap.get(pattern);
                maxLength = Math.max(maxLength, length);
            } else {
                // 只记录模式首次出现的位置
                patternMap.put(pattern, i);
            }
        }
        
        return maxLength;
    }
    
    public static void main(String[] args) {
        // 测试案例
        System.out.println(longestBalancedSubstring("abc"));       // 3
        System.out.println(longestBalancedSubstring("abac"));    // 3
        System.out.println(longestBalancedSubstring("aaabbb"));    // 6
        System.out.println(longestBalancedSubstring("aaabb"));     // 4
        System.out.println(longestBalancedSubstring("a"));         // 1
        System.out.println(longestBalancedSubstring("abccba"));    // 6
        System.out.println(longestBalancedSubstring("aaabbbc"));   // 6
    }
}
